package com.zyk.grate_offer.class04;

/**
 * 生成长度为size的达标数组，什么叫达标？
 * 达标：对于任意的 i<k<j，满足 [i] + [j] != [k] * 2
 * 给定一个正数size，返回长度为size的达标数组
 *
 * @author zhangsan
 * @date 2021/4/30 9:53
 */
public class Code06_MakeNo {

    // 分治做的
    // i*2, j*2, i*2+1, j*2+1       size:1 -- 1     size:2 --  2 3      size: 4--   4 5 6 7     size:8 -- 8 10 12 14 9 11 13 15
    // 所以就是i,j 达标.  ｉ＊２，　ｊ＊２，　ｉ＊２＋１，　ｊ＊２＋１  组成的答案一定也达标
    public static int[] makeNo(int size) {
        if (size == 1) return new int[]{1};

        int halfSize = (size + 1) >> 1; // 一半的大小, 向上取整, 如果我只要7个我生成八个, 不要最后一个就行了
        int[] base = makeNo(halfSize);
        int[] ans = new int[size];
        int index = 0;
        for (; index < halfSize; ) {
            ans[index] = base[index++] << 1;
        }
        for (int i = 0; index < size; i++) {
            ans[index++] = base[i] << 1 | 1;
        }
        return ans;
    }

    // 检验函数
    public static boolean isValid(int[] arr) {
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            for (int k = i + 1; k < N; k++) {
                for (int j = k + 1; j < N; j++) {
                    if (arr[i] + arr[j] == 2 * arr[k]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {

        System.out.println("test begin");
        for (int N = 1; N < 1000; N++) {
            int[] arr = makeNo(N);
            if (!isValid(arr)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test end");
        System.out.println(isValid(makeNo(1042)));
        System.out.println(isValid(makeNo(2981)));
    }

}
